#include <iostream>

namespace me
{
    template <typename T>
    class vector
    {
        using pointer = T*;
        using iterator = T*;
        using const_iterator = const T*;
    public:
        vector()
            :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
        {}

        vector(size_t n, const T& value = T())
            :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
        {
            reserve(n);
            for(size_t i=0; i<n; i++) {
                new(_start+i) T(value);
            }
            _finish = _start + n;
        }

        ~vector()
        {
            for(size_t i=0; i<size(); i++) {
                _start[i].~T();
            }
            operator delete(_start);
            _start = _finish = _end_of_storage = nullptr;
        }

        vector(const vector& v)
            :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
        {
            reserve(v.size());
            size_t sz = v.size();
            for(size_t i=0; i<sz; i++) {
                new(_start+i) T(v[i]);
            }
            _finish = _start + sz;
        }

        vector(vector&& v)
            :_start(v._start), _finish(v._finish), _end_of_storage(v._end_of_storage)
        {
            v._start = v._finish = v._end_of_storage = nullptr;
        }

        vector& operator=(vector v)
        {
            if(this != &v) {
                swap(v);
            }
            return *this;
        }

        vector& operator=(vector&& v)
        {
            if(this != &v) {
                swap(v);
            }
            return *this;
        }

        T& operator[](size_t pos) { return _start[pos]; }
        const T& operator[](size_t pos) const { return _start[pos]; }

        void push_back(const T& value)
        {
            if(_finish == _end_of_storage) reserve(capacity() == 0 ? 1 : 2 * capacity());
            new(_finish) T(value);
            _finish++;
        }

        iterator insert(iterator pos, const T& value)
        {
            /* 如果发生扩容，pos会失效，指向已经释放得空间需要进行更新
               记录之前pos和_start中间的元素个数
               扩容完成后，_start更新，此时_start+gap就是新的pos位置
            */
            size_t gap = pos - _start;
            if(_finish == _end_of_storage) {
                reserve(capacity() == 0 ? 1 : 2 * capacity());
                pos =  _start + gap;
            }

            /* 要将pos及之后的元素都向后挪*/
            iterator end = _finish;
            while(end > pos) {
                *(end) = *(end - 1);
                end--;
            } 
            new(pos) T(value);
            ++_finish;
            return pos;
        }

        void pop_back() { return erase(end() - 1); }
        iterator erase(iterator pos)
        {
            if(pos < _start || pos >= _finish) return _finish;

            /*如果是自定义类型，需要将pos位置对应的元素释放掉，手动调用析构*/
            pos->~T();

            /*将pos位置之后的元素都向前挪*/
            iterator end = pos + 1;
            while(end != _finish) {
                *(end - 1) = *(end);
                end++;
            }
            --_finish;
            return pos;
        }

        void reserve(size_t n)
        {
            if(n <= capacity()) return;

            /*开辟新空间，只开空间，初始化交给后面，避免因为T类型没有默认构造而出错*/
            pointer tmp = static_cast<pointer>(operator new(n*sizeof(T)));

            /*拷贝内容，要进行深拷贝，否则当T是自定义类型时可能导致多次析构的问题*/
            size_t sz = size();
            for(size_t i=0; i<sz; i++) {
                new(tmp + i) T(_start[i]); // pleacement new
            }

            /* 如果原空间存储的是自定义类型，需要显示调用析构*/
            for(size_t i=0; i<sz; i++) {
                _start[i].~T();
            }

            /*释放旧空间*/
            operator delete(_start);

            /*更新指针指向*/
            _start = tmp;
            _finish = tmp + sz;
            _end_of_storage = tmp + n;
        }

        iterator begin() { return _start; }
        iterator end() { return _finish; }
        const_iterator cbegin() const { return _start; }
        const_iterator cend() const { return _finish; }

        size_t size() const { return _finish - _start; }
        size_t capacity() const { return _end_of_storage - _start; }
        bool empty() { return _finish == _start; }
        void clear() { _finish = _start; }
    private:
        void swap(vector& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_end_of_storage, v._end_of_storage);
        }
    private:
        pointer _start;
        pointer _finish;
        pointer _end_of_storage;
    };
}

int main()
{
    me::vector<int> iv;
    iv.push_back(1);
    iv.push_back(2);
    iv.push_back(3);
    iv.push_back(4);
    iv.push_back(5);
    for(auto e : iv)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
    std::cout << iv.size() << std::endl;
    std::cout << iv.capacity() << std::endl;

    iv.insert(iv.begin(), 100);
    iv.insert(iv.begin(),200);
    for(auto e : iv)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
    std::cout << iv.size() << std::endl;
    std::cout << iv.capacity() << std::endl;

    iv.insert(iv.begin() + 2, 9999);
    for(auto e : iv)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
    std::cout << iv.size() << std::endl;
    std::cout << iv.capacity() << std::endl;
    return 0;
}